//栈的链表实现
#include "Stack2.h"
#include <stdio.h>
#include <stdlib.h>

struct Node {
    ElementType Element;
    struct Node* Next;
};

int IsEmpty(Stack S) {
    return S->Next ? 0 : 1;
}

Stack CreateStack() {
    //建立链表
    Stack s = (Stack)malloc(sizeof(struct Node));
    s->Next = NULL;
    return s;
}

void DisposeStack(Stack S) {
    //先MakeEmpty栈，在释放S头节点即可
    MakeEmpty(S);
    free(S);
}

void MakeEmpty(Stack S) {
    //此算法比较巧妙
    pNode temp = S->Next, temp2;
    S->Next = NULL;

    while (temp) {
        temp2 = temp->Next;
        free(temp);
        temp = temp2;
    }
}

//声明一个规则：从链表头部入栈和出栈
void Push(ElementType x, Stack S) {
    //构造该节点
    pNode pn = (pNode)malloc(sizeof(struct Node));
    pn->Element = x;
    pn->Next = S->Next;
    S->Next = pn;
}

ElementType Pop(Stack S) {
    ElementType res = (ElementType)0;
    if (S->Next) {
        res = S->Next->Element;
        //删除此头元素
        pNode temp = S->Next;
        S->Next = temp->Next;
        free(temp);
    }
    return res;
}

ElementType Top(Stack S) {
    if (S->Next) {
        return S->Next->Element;
    }
    return (ElementType)0;
}

void TestStack2() {
    Stack s = CreateStack();

    for (int i = 0; i < 10; i++) {
        Push(i, s);
    }

    while (!IsEmpty(s)) {
        printf("%d\n", Pop(s));
    }

    DisposeStack(s);
}